package 剑指offer;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.HashMap;

public class p39数组中出现次数超过一半的数字 {
    //哈希表统计法
    public int majorityElement1(int[] nums) {
        HashMap<Integer,Integer> map=new HashMap<>();
        int len=nums.length;

        for(int num:nums) {
            //put()方法 如果插入 key 对应的value 已经存在，则执行 value替换操作，返回旧的 value 值；如果不存在则执行插入，返回 null。
            map.put(num,map.getOrDefault(num,0)+1);
            //getOrDefault()方法 获取指定 key 对应对 value，如果找不到 key ，则返回设置的默认值。
        }

        for (int i = 0; i <len; i++) {
            if (map.get(nums[i]) > len/2) {
                //get()方法 返回指定 key 对应的 value。
                return nums[i];
            }
        }

        return -1;
    }

    //数组排序法：经过排序的数组，中位数一定是出现次数 大于 数组长度一半的数
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }
}
